package com.mypaper.schedule;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;

import com.mypaper.dag.RefactorDAG;
import com.mypaper.elem.LinkedListNode;
import com.mypaper.elem.PairElement;
import com.mypaper.elem.ScheduleElement;
import com.mypaper.elem.ScheduleNode;
import com.mypaper.elem.TaskAttribute;
import com.mypaper.elem.TaskNode;
import com.mypaper.list.OrderLinkedList;
import com.mypaper.list.ScheduleResults;

public class HTRSchedule
{
	public ScheduleResults scheduleResults;
	public int[] assiProc2Task;//任务分配到的处理器号；
	public int[][] MIIP;//任务的数据到达最晚的父节点
	public float[] AST;//实际开始时间；
	public float[] AFT;//实际结束时间；
	public int[] reliedDup;//依赖的任务编号；
	public int[] inDegree;//dag入度；
	OrderLinkedList[] idleTimeList;//处理器空闲时间表;
	ArrayList<TaskAttribute> readyQueue;//准备队列的任务;
	float[][] readyTime;//任务在每个处理器上数据的准备时间点;
	float[] taskReadyTime;//每个任务在处理器上的准备时间平均值；
	float[][] DAT;//父节点数据到达时间;
	boolean[][] isScheduled;//任务是否在某处理器上被调度;
	boolean[] taskIsScheduled;//任务是否已被调度；
	public float[][] MST;//添加到当前任务之前的准备任务开始时间；
	public float[][] MFT;//添加到当前任务之前的准备任务结束时间;
	public float[][] EST;//每个任务遍历每个处理器的最早开始时间；
	public float[][] EFT;//每个任务遍历每个处理的最早完成时间；
	public float[] nowtimeLevel;//任务的实时优先级
	
	public HTRSchedule(RefactorDAG dag)
	{
		scheduleResults = new ScheduleResults();
		assiProc2Task = new int[dag.vertexNum];
		MIIP = new int[dag.vertexNum][dag.procNum];
		AST = new float[dag.vertexNum];
		AFT = new float[dag.vertexNum];
		reliedDup = new int[dag.vertexNum];
		inDegree = new int[dag.vertexNum];
		idleTimeList = new OrderLinkedList[dag.vertexNum];
		for(int i = 0; i < dag.procNum; i++)
		{
			idleTimeList[i] = new OrderLinkedList();
			idleTimeList[i].insertNode(new PairElement(0,Float.MAX_VALUE));
		}
		readyQueue = new ArrayList<TaskAttribute>();
		readyTime = new float[dag.vertexNum][dag.procNum];
		DAT = new float[dag.vertexNum][dag.procNum];
		isScheduled = new boolean[dag.vertexNum][dag.procNum];
		MST = new float[dag.vertexNum][dag.procNum];
		MFT = new float[dag.vertexNum][dag.procNum];
		EST = new float[dag.vertexNum][dag.procNum];
		EFT = new float[dag.vertexNum][dag.procNum];
		nowtimeLevel = new float[dag.vertexNum];
		taskIsScheduled = new boolean[dag.vertexNum];
		taskReadyTime = new float[dag.vertexNum];
	}
	
	@SuppressWarnings("null")
	public void HTR_Algrithm(RefactorDAG dag)
	{
		for(int i = 0; i < dag.vertexNum; i++)
		{
			inDegree[i] = dag.inDegree[i];
			AST[i] = Float.MAX_VALUE;
			AFT[i] = Float.MAX_VALUE;
			reliedDup[i] = -1;
			assiProc2Task[i] = -1;
			nowtimeLevel[i] = 0;
			taskIsScheduled[i] = false;
			taskReadyTime[i] = (float) 0.0;
			for(int j = 0; j < dag.procNum; j++)
			{
				MST[i][j] = Float.MAX_VALUE;
				MFT[i][j] = Float.MAX_VALUE;
				EST[i][j] = Float.MAX_VALUE;
				EFT[i][j] = Float.MAX_VALUE;
				MIIP[i][j] = -1;
				DAT[i][j] = 0;
				isScheduled[i][j] = false;
				readyTime[i][j] = 0;
				
			}
		}
		int currentTaskIndex = -1;
        float EFT_back = Float.MAX_VALUE;
        ArrayList<TaskAttribute> readyQueue = new ArrayList<TaskAttribute>();
		PairElement searchItem = new PairElement();
		PairElement beFoundItem = new PairElement();
		OrderLinkedList[] idleTimeListBack = new OrderLinkedList[dag.procNum];
		OrderLinkedList idleTimeListBackIn = new OrderLinkedList();
		idleTimeListBackIn.insertNode(new PairElement(0,Float.MAX_VALUE));
		
		for(int i = 0; i < dag.procNum; i++){
			idleTimeListBack[i]=new OrderLinkedList();
			idleTimeListBack[i].insertNode(new PairElement(0,Float.MAX_VALUE));
		}
		
		TaskNode currentTask=dag.priorHTR.first;
		
		while(currentTask != null)
		{
			currentTaskIndex = currentTask.info.index;
			if(taskIsScheduled[currentTaskIndex] == false)
			{
				//找到当前任务的MIIP和任务起始时间
				for(int i = 0; i < dag.procNum; i++)
				{
					for(int j = 0; j < dag.vertexNum; j++)
					{
						if(dag.edgeWeight[j][currentTaskIndex] != 0)
						{
							if(assiProc2Task[j] == i)//父节点在同一处理器上，节点数据到达时间等于父节点完成时间
							{
								DAT[j][i] = AFT[j];
							}else
							{
								DAT[j][i] = AFT[j] + dag.edgeWeight[j][currentTaskIndex];//不在同一处理器则加上通信量
							}
							
							if(readyTime[currentTaskIndex][i] < DAT[j][i])
							{
								readyTime[currentTaskIndex][i] = DAT[j][i];
								MIIP[currentTaskIndex][i] = j;//找关键父母
							}
						}
					}
				}
				TaskNode queueListTask = currentTask;
				//readyQueue = null;
//////////////////////////////
				if(readyQueue != null)readyQueue.clear();//清除队列中的任务；
				while(queueListTask != null)//将入度为0的节点加入准备队列中
				{
					int queueTaskIndex = queueListTask.info.index;
					if(inDegree[queueTaskIndex] == 0 && taskIsScheduled[queueTaskIndex] == false && queueTaskIndex != currentTaskIndex)
					{
						TaskAttribute queueTask = new TaskAttribute(queueTaskIndex, queueListTask.info.weightPrior);
						readyQueue.add(queueTask);
					}
					queueListTask = queueListTask.next;
				}
				Iterator<TaskAttribute> iterator = readyQueue.iterator();
				int canTaskIndex = -1;
				double canTaskBlevel = 0.0;
////取出准备队列中的优先级最高的候选任务：
				while(iterator.hasNext())
				{
					TaskAttribute canTask = (TaskAttribute) iterator.next();
		//找到队列中任务在每个处理器上的准备时间和其关键父母:
					for(int i = 0; i < dag.procNum; i++)
					{
						for(int j = 0; j < dag.vertexNum; j++)
						{
							if(dag.edgeWeight[j][canTask.index] != 0)
							{
								if(assiProc2Task[j] == i)//父节点在同一处理器上，节点数据到达时间等于父节点完成时间
								{
									DAT[j][i] = AFT[j];
								}else
								{
									DAT[j][i] = AFT[j] + dag.edgeWeight[j][canTask.index];//不在同一处理器则加上通信量
								}
								
								if(readyTime[canTask.index][i] < DAT[j][i])
								{
									readyTime[canTask.index][i] = DAT[j][i];
									MIIP[canTask.index][i] = j;//找关键父母
								}
							}
						}
					}
		//计算任务在处理器上的平均准备时间:			
					for(int i = 0; i < dag.procNum; i++)
					{
						taskReadyTime[canTask.index] += readyTime[canTask.index][i];
					}
					taskReadyTime[canTask.index] = taskReadyTime[canTask.index]/(float)dag.procNum;
					
				}
    //将当前任务在处理器上遍历，找到最早完成时间的处理器
				for(int k = 0; k < dag.procNum; k++)
				{
					boolean found = false;
					idleTimeListBack[k].copyList(idleTimeList[k]);
					LinkedListNode currentIdle = idleTimeListBack[k].first;
					while(currentIdle != null && !found)
					{
						//找合适的空闲时间
						searchItem.setNum(readyTime[currentTaskIndex][k], readyTime[currentTaskIndex][k] + dag.vertexWeight[currentTaskIndex][k]);
						beFoundItem = (PairElement)idleTimeList[k].search(searchItem);
						if(beFoundItem != null)
						{
							found = true;
						}
						currentIdle = currentIdle.next;
					}
					if(found == true)
					{
						EST[currentTaskIndex][k] = Math.max(readyTime[currentTaskIndex][k], beFoundItem.start);
						EFT[currentTaskIndex][k] = EST[currentTaskIndex][k] + dag.vertexWeight[currentTaskIndex][k];
						idleTimeListBack[k].deleteNode(beFoundItem);
						if(searchItem.start > beFoundItem.start)
						{
							idleTimeListBack[k].insertNode(new PairElement(beFoundItem.start,EST[currentTaskIndex][k]));
							idleTimeListBack[k].insertNode(new PairElement(EFT[currentTaskIndex][k],beFoundItem.end));
						}else
						{
							idleTimeListBack[k].insertNode(new PairElement(EFT[currentTaskIndex][k],beFoundItem.end));
						}
						if(EFT_back > EFT[currentTaskIndex][k])
						{
							assiProc2Task[currentTaskIndex] = k;
							EFT_back = EFT[currentTaskIndex][k];
							AFT[currentTaskIndex] = EFT_back;
							AST[currentTaskIndex] = AFT[currentTaskIndex] - dag.vertexWeight[currentTaskIndex][k];
						}
						
					}
					
				}
		//从剩余任务队列中寻找任务填入前面空隙中		
				int currProc = assiProc2Task[currentTaskIndex];//记录当前任务的处理器；
				Iterator<TaskAttribute> it = readyQueue.iterator();
				ArrayList<TaskAttribute> insertList = new ArrayList<TaskAttribute>();
				while(it.hasNext())//给队列中能够插入到当前任务前的任务进行优先级计算
				{
					TaskAttribute insertTask = (TaskAttribute)it.next();
					double insertLevel = insertTask.weightPrior + taskReadyTime[insertTask.index];
					//if(insertTask.index != canTaskIndex)
						insertList.add(new TaskAttribute(insertTask.index,insertLevel));
				}
				Collections.sort(insertList, new LevelSort());//给待插入的任务进行优先级排序；
				//System.out.println("sort,insertList:"+insertList);
				Iterator<TaskAttribute> taskList = insertList.iterator();
				try
				{
					idleTimeListBackIn.copyList(idleTimeListBack[currProc]);
				} catch (Exception e)
				{
					System.out.println("currProc:"+currProc);
					//e.printStackTrace();
				}
				boolean foundIn = false;
				PairElement searchIn = new PairElement();
				PairElement beFoundIn = new PairElement();
				LinkedListNode currentIdle = idleTimeListBackIn.first;
				int insertedTaskIndex = -1;
				while(taskList.hasNext())
				{
					foundIn = false;
					TaskAttribute insertTask = (TaskAttribute)taskList.next();
					while(currentIdle != null && !foundIn)
					{
						searchIn.setNum(readyTime[insertTask.index][currProc], readyTime[insertTask.index][currProc] + dag.vertexWeight[insertTask.index][currProc]);
						beFoundIn = (PairElement)idleTimeList[currProc].search(searchIn);
						if(beFoundIn != null)foundIn = true;
						currentIdle = currentIdle.next;
					}
					if(foundIn == true)
					{if(1==1)break;
						EST[insertTask.index][currProc] = Math.max(readyTime[insertTask.index][currProc], beFoundIn.start);
						EFT[insertTask.index][currProc] = EST[insertTask.index][currProc] + dag.vertexWeight[insertTask.index][currProc];
						if(EFT[insertTask.index][currProc] <= AST[currentTaskIndex])
						{
							if(searchIn.start > beFoundIn.start)
							{
								idleTimeListBackIn.insertNode(new PairElement(beFoundIn.start,EST[insertTask.index][currProc]));
								idleTimeListBackIn.insertNode(new PairElement(EFT[insertTask.index][currProc], beFoundIn.end));
							}
							else
								idleTimeListBackIn.insertNode(new PairElement(EFT[insertTask.index][currProc], beFoundIn.end));
							insertedTaskIndex = insertTask.index;
							AFT[insertedTaskIndex] = EFT[insertTask.index][currProc];
							AST[insertedTaskIndex] = EFT[insertTask.index][currProc] - dag.vertexWeight[insertTask.index][currProc];
							assiProc2Task[insertTask.index] = currProc;
							isScheduled[insertTask.index][currProc] = true;
							taskIsScheduled[insertTask.index] = true;
							ScheduleElement perTask = new ScheduleElement();
							perTask.setNum(insertedTaskIndex, currProc, EST[insertTask.index][currProc], EFT[insertTask.index][currProc]);
							scheduleResults.insertNode(perTask);
							for(int i = 0; i < dag.vertexNum; i++)
							{
								if(dag.edgeWeight[insertedTaskIndex][i] != 0)
								{
									inDegree[i]--;
								}
							}
							System.out.println("HTR将任务："+ insertedTaskIndex + " 在处理器proc." + currProc + " 上插入到任务" + currentTaskIndex + "之前" +" ，调度时间：[" + AST[insertedTaskIndex] + "," + AFT[insertedTaskIndex] + "]");
							break;
						}
					}
					
				}
				if(insertedTaskIndex != -1)
				{
					idleTimeListBack[currProc].copyList(idleTimeListBackIn);
				}
				EFT_back = Float.MAX_VALUE;
				isScheduled[currentTaskIndex][currProc] = true;
				taskIsScheduled[currentTaskIndex] = true;
				idleTimeList[currProc].copyList(idleTimeListBack[currProc]);
				ScheduleElement perTask = new ScheduleElement();
				perTask.setNum(currentTaskIndex, currProc, AST[currentTaskIndex], AFT[currentTaskIndex]);
				scheduleResults.insertNode(perTask);
				for(int i = 0; i < dag.vertexNum; i++)
				{
					if(dag.edgeWeight[currentTaskIndex][i] != 0)
					{
						inDegree[i]--;
					}
				}
			}
			//System.out.println("HTR当前调度任务："+ currentTaskIndex + " 在处理器proc." + assiProc2Task[currentTaskIndex] +" 上，调度时间：[" + AST[currentTaskIndex] + "," + AFT[currentTaskIndex] + "]");
			currentTask = currentTask.next;
		}
		
	}
	class LevelSort implements Comparator{
		@Override
		public int compare(Object o1, Object o2)
		{
			int c = 0;
			double o1Level = ((TaskAttribute)o1).weightPrior ;
			double o2Level = ((TaskAttribute)o2).weightPrior;
			if(o1Level - o2Level > 0)
			{
				c = -1;
			}
			else if(o1Level - o2Level < 0)
				c = 1;
			else c = 0;
			return c;
		}

	}
	public float makespan(){
		float curr=0;
		ScheduleNode currentTask=scheduleResults.first;
		while(currentTask!=null){
			if(curr<currentTask.info.endTime)
				curr=currentTask.info.endTime;
			currentTask=currentTask.next;
		}
		return curr;
	}

}
